The present invention relates to a method of and apparatus for data distribution wherein a large amount of data or work units are equally distributed among a plurality of memories which constitute a memory group, thereby enabling parallel processing of a large amount of data or work units.
FIG. 5 shows a coupling unit that is employed in a conventional data distributing apparatus, which is disclosed, for example, in Electronic Communication Society Proceedings Vol. J86-D, No. 6, p. 1272.
Referring to FIG. 5, reference numeral 1 denotes a coupling unit; 2 and 3, two data input lines of the coupling unit 1; 4 and 5, two data output lines of the coupling unit 1; and 6, a switch which realizes either one of the two connection patterns, that is, a first pattern in which the input lines 2 and 3 are connected to the output lines 4 and 5, respectively, (hereinafter referred to as "parallel pattern"), and a second pattern in which the input lines 2 and 3 are connected to the output lines 5 and 4, respectively, (hereinafter referred to as "cross pattern"), in response to a data connection pattern change-over signal that is delivered from a controller (denoted by reference numeral 10 in FIG. 4).
FIG. 6 shows the two data connection patterns that are alternatively realized by the switch 6 inside the coupling unit 1. FIG. 4 shows the general arrangement of a typical conventional data distributing apparatus. Reference numeral 7 in FIG. 4 denotes a data distributing apparatus, 8 a first memory group, 9 a second memory group, and 10 a controller that controls data distribution.
In the system shown in FIG. 4, coupling units 1 are arranged in a matrix comprising 4.times.3 rows. This is because the first memory group 8 comprises 8 memories and it is therefore necessary to provide 4 units (each having two input lines) in each vertical row and log.sub.2 8=3 rows in each horizontal row. Generally, it is necessary in order to distribute data equally by use of a first group of N memories and a second group of N memories to form a data distributing apparatus comprising a group of coupling units which are arranged in a matrix of (N/2).times.log.sub.2 N rows. It should be noted that there are various other methods of arranging a network which comprises a plurality of coupling units and that the technique according to the present invention may be similarly effectively applied to these methods. The details of the coupling unit arrangement shown in FIG. 4 and other coupling unit arrangements are explained in the report of the above-mentioned Electronic Communication Society Proceedings.
The first memory group 8 stores at least data which is to be processed. The second memory group 9 is used as a temporary memory area for processing data stored in the first memory group 8. A plurality of coupling units 1 are adapted to equally distribute the data in the first memory group 8 to the second memory group 9 according to a predetermined rule.
An example operation will next be explained. For the sake of the description, it is assumed that the object of distribution is data only and data is transferred from the first group 8 of N memories to the second group 9 of N memories after being classified into K different kinds of data. The object of the data distributing apparatus is to equally distribute data stored in the first memory group 8 to the second group 9 of N memories for each kind of data. More specifically, each piece of data belongs to one of the K different kinds of data, i.e., from 0 to K-1. It is assumed that the total number of data of the X-th (X=0, . . . , K-1) kind is N.sub.X and the N.sub.X of data is transferred from the first memory group 8 to the second memory group 9. In such a case, the object of the data distributing apparatus is to realize a condition in which each of the memories in the second memory group 9 has N.sub.X /K of data stored therein upon the completion of the data transfer, for all the X (X=0, . . . , K-1) kinds of data.
As the data distribution operation is started, data is successively sent from the first group of memories 8 to either the input lines 2 or 3 of the coupling units 1 in the first row, which are connected with the first memory group 8. Each coupling unit 1 in the first row sets either one of the two patterns for the switch 6 shown in FIG. 6 according to an instruction from the data distribution controller 10 to move the input data in accordance with the set pattern, thereby transferring the data to one of the coupling units 1 in the second row which is connected to the coupling unit 1 concerned, through either the output line 4 or 5. The coupling units 1 in the second row and those in the rows following repeat a similar operation. Data that is outputted through either the output line 4 or 5 of each coupling unit 1 which belongs to the final row is stored in the corresponding memory in the second memory group 9 while being arranged according to kind.
The data distribution controller 10 holds administrative information that indicates the number of data of each kind which have been distributed to each memory in the second memory group 9, thereby controlling the equal distribution of data at all times. Accordingly, assuming that the kind of data sent from the first memory group 8 is represented by X, the controller 10 selects from amoung the memories in the second memory group 9 one to which data of the kind X have been least distributed up to now, and controls the connection of the coupling units 1 so that the relevant data is transferred to the selected memory in the second group 9, thereby eventually providing equal distribution of data for each kind.
In the conventional data distributing apparatus stated above, the data distribution controller 10 needs to determine a connection pattern for the switches 6 of all the coupling units 1 for every data transfer operation during the data distribution and to inform the coupling units 1 of the determined patterns, and this remarkably lowers the efficiency of the data distribution processing. Another problem of the prior art apparatus is that, as the number of memories in the first and second groups and the number of coupling units increase, the load of distribution control concentrates on the data distribution controller 10, so that the processing performance is likely to substantially deteriorate. In the distribution of work units also, the prior art apparatus stated above suffers from the same problems.
In view of the above-described problems of the prior art, it is an object of the present invention to provide a data distributing method which enables an improvement in the efficiency of the data or work unit distribution processing and which is free from the problem of deterioration in the performance of data or work unit distribution processing even when the number of memories in the first and second groups and the number of coupling units increase, and also provide a data distributing apparatus which is effectively employed to carry out the data distributing method.
The following sentences are given for references:
(1) The present invention is a data distributing method which is designed so that data (or work units) which is classified into a plurality of kinds is distributed equally for each kind, as shown in FIG. 3. In addition, the present invention provides an apparatus for this data distributing method. More specifically, in a data base processing operation (e.g., a retrieval processing of a large amount of data), data in a first group of memories is classified into a plurality of kinds and then equally distributed to a second group of memories for each kind [this feature will be hereinafter referred to as (A)], thereby enabling high-speed parallel processing by a plurality of processors which are provided separately. PA0 (2) The data distributing apparatus according to the present invention comprises a plurality of coupling units, which transfer a plurality of input data to a plurality of output destinations by changing over data connection patterns of respective internal switches. More specifically, each coupling unit is provided with a group of counters for counting and storing a cumulative number of data for each kind of data, and the connection pattern change-over control is effected on the basis of the counts of these counters, thus determining an output destination for each piece of input data. In other words, each coupling unit individually determines an output destination of each piece of input data by use of the counts of its own counters [this feature will be hereinafter referred to as (B)]. By doing so, the equal distribution of data for each kind, which is stated in the above paragraph (1), can be made efficiently. In the present invention, each piece of data may be sent to any desired memory, and it is only desired to achieve equal distribution of data for each kind [this feature will be hereinafter referred to as (C)].
Accordingly, a prior art wherein each piece of data is given the address of a device of final transfer destination, which is disclosed, for example, in Japanese Patent Public Disclosure (KOKAI) No. 62-54350 (1987), is different from the present invention in the object with regard to the above feature (A). Regarding the above feature (C), the prior art is different from the present invention in premised scope. In the prior art, control information that is required to switch the coupling units is obtained from an address that is given to each piece of data to be transferred, which is different from the above feature (B). In addition, the applicable field of the prior art is confined to data communication.
A prior art that is disclosed in Japanese Patent Public Disclosure (KOKAI) No. 62-21398 (1987) is adapted for data communication, which is a different field from data base processing. The object of this prior art is different from that of the present invention with regard to the above features (A) and (C). In addition, control data that is employed to switch the coupling units is given as a part of data, which is also different from the above feature (B).
Further, a prior art that is disclosed in Japanese Utility Model Public Disclosure (KOKAI) No. 61-83392 (1986) is different from the present invention in that it is adapted to handle image signals. In this prior art, the transfer of a single input to a multiplicity of outputs is controlled with a single gate, which is different from the data transfer carried out in the present invention in which a plurality of inputs are transferred to a plurality of outputs through a multiplicity of coupling units. Although this prior art is the same as the present invention in that a counter is employed for distribution of data, the counter in the prior art is not adapted to execute counting with regard to the kind of data and the object of this prior art is not the equal distribution of data.